package jacktgq.mineSweeper;

/**
 * @Author CandyWall
 * @Date 2021/3/28--14:05
 * @Description 算法的随机性评估
 */
public class RandomAlgorithmAssessment {
    /**
     *
     * @param N         ：统计次数
     * @param n         ：格子的总数
     * @param m         ：雷的总数
     * @param name      ：算法名称
     * @param algorithm ：算法实现
     */
    public static void assess(int N, int n, int m, String name, RandomAlgorithm algorithm) {
        if (N < 0) {
            throw new IllegalArgumentException("统计次数必须大于0！");
        }
        if (m > n) {
            throw new IllegalArgumentException("雷的总数不能超过格子的总数！");
        }

        // 统计每一个位置上雷出现的频率
        int[] freq = new int[n];

        // 记录雷的分布，如果数组中某个位子上有雷，记为1，没有雷，记为0
        int[] arr = new int[n];
        // 进行N次统计
        for (int i = 0; i < N; i++) {
            // 每次需要将m个雷放在数组的头部
            for (int j = 0; j < m; j++) {
                arr[j] = 1;
            }
            for (int j = m; j < n; j++) {
                arr[j] = 0;
            }
            // 调用随机算法打乱顺序
            algorithm.shuffle(arr, m);
            for (int j = 0; j < n; j++) {
                freq[j] += arr[j];
            }
        }

        System.out.println("通过" + name + "，各个格子中雷出现的频率如下：");
        for (int i = 0; i < n; i++) {
            System.out.println(i + " : " + freq[i] * 1.0 / N);
        }
    }

    /**
     * 交换数组中两个位置上的值
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int N = 1000_0000;
        int n = 10;
        int m = 5;
        assess(N, n, m, "随机算法1", (arr, mineNumber) -> {
            // 随机算法1：将每一个格子上的值和随机的格子上的值进行交换
            for (int i = 0; i < arr.length; i++) {
                int j = (int) (Math.random() * arr.length);
                swap(arr, i, j);
            }
        });

        assess(N, n, m, "随机算法2", (arr, mineNumber) -> {
            // 随机算法2：将每一个雷所在的格子上的值和随机的格子上的值进行交换
            for (int i = 0; i < mineNumber; i++) {
                int j = (int) (Math.random() * arr.length);
                swap(arr, i, j);
            }
        });

        assess(N, n, m, "Knuth1", (arr, mineNumber) -> {
            // knuth算法1，从[i, arr.length)区间中随机获取元素，然后和第i个元素交换
            for (int i = 0; i < arr.length; i++) {
                int j = (int) (Math.random() * (arr.length - i) + i);
                swap(arr, i, j);
            }
        });

        assess(N, n, m, "Knuth2", (arr, mineNumber) -> {
            // knuth算法2：knuth算法的另一种写法，从[0, i+1)区间中随机获取元素，然后和第i个元素交换
            for (int i = arr.length - 1; i >= 0; i--) {
                int j = (int) (Math.random() * (i + 1));
                swap(arr, i, j);
            }
        });

    }
}

@FunctionalInterface
interface RandomAlgorithm {
    void shuffle(int[] arr, int mineNumber);
}
